/*!
 * \file MultiLevelDirectlyAddressedSet.h
 * \brief A multilevel bitmap data structure.
 *
 * \date Jun 18, 2012
 * \author correa
 */

#ifndef MULTILEVELDIRECTLYADDRESSEDSET_H_
#define MULTILEVELDIRECTLYADDRESSEDSET_H_

#include <stdlib.h>
#include <stdio.h>
#include "BitTools.h"
#include "BitMapDirectlyAddressedSet.h"

/*! \class MultiLevelDirectlyAddressedSet
 * \brief An implementation of DirectlyAddressedSet using a static multilevel bitmap as data structure.
 *
 * This class is specially designed to provide fast enumeration of the set or the entire universe.
 * For this purpose, this class stores one bit for each element of the universe. If the bit of an element
 * equals 1, then this element is in the set. Otherwise, this element is in the complement.
 *
 * Each level of the this object is itself a BitMapDirectlyAddressedSet in order to make the implementation of the classes
 * that inherit from DirectlyAddressedSet easier. This class has almost all the public methods implemented, a
 * child class only need to implement the protected ones.
 *
 * \tparam T the type of a word
 */
template <typename T>
class MultiLevelDirectlyAddressedSet : public BitMapDirectlyAddressedSet<T> {
	friend class MultiIterator;

protected:

	long							h;		//!< number of levels
	BitMapDirectlyAddressedSet<T>** level;	//!< levels of the structure

public:

	/*!
	 * \brief The base constructor.
	 *
	 * It is to be used in the children classes to make same calculation about the size of the type T.
	 *
	 * \param size the size of the universe.
	 */
	MultiLevelDirectlyAddressedSet(long size);

	/*! \class MultiLevelDirectlyAddressedSet::MultiIterator
	 * \brief A generic iterator on the set of elements.
	 *
	 * The elements are enumerated in an increasing order.
	 *
	 * An object of this class keeps the state of an enumeration. This means that various enumerations can
	 * be performed simultaneously provided that each of them is associated with a different iterator.
	 *
	 * The path from the root of the tree until last element enumerated is composed by nodes of the vEBTree.
	 * A binary search in this path using min and max information of subtrees allows a \f$O(\log \log n)\f$
	 * time complexity for each access.
	 *
	 */
	class MultiIterator : public DirectlyAddressedSet::Iterator, protected BitTools<T> {
	protected:
		long											idxInNextNode;	//!< result of last call to next() or nextUpTo() at a level
		const long										height;			//!< number of levels
		DirectlyAddressedSet::Iterator ** const			levelit;		//!< iterator for each level

		/*!
		 *  \brief A constructor for a specified enclosed MultiLevelDirectlyAddressedSet<T>.
		 *
		 *  The instance created with this constructor acts on the levels of the specified MultiLevelDirectlyAddressedSet<T>. This
		 *  is a static parameter, which means that this iterator is not affected by further modifications on the number of levels.
		 *  In special, if this number of levels is reduced, an error may occur during the enumeration with this iterator.
		 *
		 *  \param t the enclosing abstract set
		 */
		MultiIterator(MultiLevelDirectlyAddressedSet<T> * t);
		/*!
		 *  \brief A constructor for a substructure of a specified enclosed MultiLevelDirectlyAddressedSet<T>.
		 *
		 *  The instance created with this constructor acts on the levels of the specified MultiLevelDirectlyAddressedSet<T>. This
		 *  is a static parameter, which means that this iterator is not affected by further modifications on the number of levels.
		 *  In special, if this number of levels is reduced, an error may occur during the enumeration with this iterator.
		 *
		 *  \param t the enclosing abstract set
		 *  \param l number of levels of the substructure of \c t
		 */
		MultiIterator(MultiLevelDirectlyAddressedSet<T> * t, long l);
		/*!
		 * \brief Constructor of a filtered iterator.
		 *
		 * The enumeration is performed with the specified filtering applied to each level.
		 *
		 * \param t the enclosing set
		 * \param fiter an iterator on the set used to filter the enumeration
		 * \param fil the filter determining the operation of filtering
		 */
		MultiIterator(MultiLevelDirectlyAddressedSet<T> * t, BitMapDirectlyAddressedSet<T> * fiter, Filter<T> * fil);

	public:
		//destructor
		~MultiIterator();

		virtual void restartFrom(long from);
		virtual long next();
		virtual long nextUpTo(long to);
	};

	/*!
	 * \brief Adds a new level to the structure (optional operation).
	 *
	 * This new level is created just above the current smallest level of the tree. The implementation
	 * of vEBTree used in this level is determined by the specified factory.
	 * If the current smallest level is 0 (the tree has all level already), then no new level is created.
	 *
	 * Realize that this method allow us to build a tree with different data structure in each level,
	 * and different relations between levels as well.
	 *
	 * \param f a factory for the implementation of the new level.
	 *
	 * \return the level added. If less than zero, then no level has been added.
	 */
	virtual long newLevel(BitMapDirectlyAddressedSetFactory<T> * f);
	virtual long height();

	/*!
	 * \brief A destructor.
	 *
	 * All data used are deleted and memory space are cleaned.
	 */
	virtual ~MultiLevelDirectlyAddressedSet();

	/*!
	 * \brief Create a copy of this object.
	 *
	 * A concrete implementation of this class must override this method in order to perform the copy of the
	 * data structure.
	 *
	 * \return a copy of this object.
	 */
	virtual DirectlyAddressedSet* clone() const = 0;
	virtual DirectlyAddressedSet::Iterator* newIterator();
	/*!
	 * \brief An iterator to the substructure composed by the specified number of levels from the bottom
	 *
	 * \param l number of levels of the substructure
	 *
	 * \return an itertor to the substructure
	 */
	virtual DirectlyAddressedSet::Iterator* newIterator(long l);
	/*!
	 * \brief Constructs a filtered iterator
	 *
	 * The returned iterator performes an enumeration with the specified filtering applied to each level.
	 *
	 * \param d a set used to filter the enumeration
	 * \param f the filter determining the operation of filtering
	 *
	 * \return a filtered iterator on this set
	 */
	virtual DirectlyAddressedSet::Iterator* newSetIterator(BitMapDirectlyAddressedSet<T> * d, Filter<T> * f);
	virtual DirectlyAddressedSet::Iterator* newComplIterator();

	/*!
	 * \brief Returns an array containing all of the elements in this set in increasing order.
	 *
	 * At the discretion of the implementation, this object may maintain a reference to the returned array.
	 * This method acts as bridge between array-based and eVBTree-based APIs.
	 * The size of the vector is returned in the pointer size.
	 *
	 * \param size a pointer to store the number of elements in the set.
	 *
	 * \return an array containing all the elements in this vEBTree.
	 *
	 */
	virtual char * toArray(long* size);

	virtual bool isEmpty();
	virtual void allToSet();
	virtual void allToCompl();
	virtual long firstInCompl();
	virtual long cardOfSet();
	virtual long cardOfCompl();

	//DEBUG
	void show();

};

template<typename T>
MultiLevelDirectlyAddressedSet<T>::~MultiLevelDirectlyAddressedSet() {
}

template<typename T>
MultiLevelDirectlyAddressedSet<T>::MultiLevelDirectlyAddressedSet(long size) : DirectlyAddressedSet(size), h(0), level(new DirectlyAddressedSet*[this->inline_ceillog(size, this->logb)+1]) {
}

template<typename T>
MultiLevelDirectlyAddressedSet<T>::MultiIterator::MultiIterator(MultiLevelDirectlyAddressedSet<T>* t) : DirectlyAddressedSet::Iterator(t), height(t->height), levelit(new DirectlyAddressedSet::Iterator*[height]) {
	int i;
	for (i = 0; i < height; i++)
		levelit[i] = t->level[i]->newIterator();
	restart();
}

template<typename T>
MultiLevelDirectlyAddressedSet<T>::MultiIterator::MultiIterator(MultiLevelDirectlyAddressedSet<T>* t, long l) : DirectlyAddressedSet::Iterator(t), height(l), levelit(new DirectlyAddressedSet::Iterator*[height]) {
	int i;
	for (i = 0; i < height; i++)
		levelit[i] = t->level[i]->newIterator();
	restart();
}

template<typename T>
MultiLevelDirectlyAddressedSet<T>::MultiIterator::MultiIterator(MultiLevelDirectlyAddressedSet<T> * t, BitMapDirectlyAddressedSet<T> * fiter, Filter<T> * fil) : DirectlyAddressedSet::Iterator(t), height(t->h), levelit(new DirectlyAddressedSet::Iterator*[height]) {
	int i;
	for (i = 0; i < height; i++)
		levelit[i] = t->level[i]->newIterator(fiter, fil);
	restart();
}

template<typename T>
MultiLevelDirectlyAddressedSet<T>::MultiIterator::~MultiIterator() {
	int i;
	for (i = 0; i < height; i++)
		delete levelit[i];
	delete[] levelit;
}

template<typename T>
inline void MultiLevelDirectlyAddressedSet<T>::MultiIterator::restartFrom(long from) {
	idxInNextNode = from + sizeof(T) - this->remainder(from);
	int l;
	for (l = 0; l < height; l++) {
		levelit[l]->restartFrom(from);
		from >>= this->logb;
	}
}

template<typename T>
inline long MultiLevelDirectlyAddressedSet<T>::MultiIterator::next() {
	long l = 0, ret;

	// up hill...
	while (l < height - 1 && (ret = levelit[l++]->nextUpTo(idxInNextNode)) >= idxInNextNode)
		idxInNextNode >>= this->logb;

	if (l == height - 1)
		ret = levelit[l]->next();

	// down hill...
	long rem;
	while (l > 0) {
		l--;
		levelit[l]->restartFrom(ret);
		ret = levelit[l]->next();
	}

	if (ret >= idxInNextNode)
		idxInNextNode = ret + sizeof(T) - this->remainder(ret);
	return ret;
}

template<typename T>
inline long MultiLevelDirectlyAddressedSet<T>::MultiIterator::nextUpTo(long to) {
	long l = 0, tto[height], ret;

	// up hill...
	tto[0] = to;
	if (to < idxInNextNode)
		idxInNextNode = to;
	while (l < height - 1 && (ret = levelit[l++]->nextUpTo(idxInNextNode)) >= idxInNextNode) {
		idxInNextNode >>= this->logb;
		tto[l+1] = tto[l] >> this->logb;
	}

	if (l == height - 1)
		ret = levelit[l]->nextUpTo(tto[l]);

	// down hill...
	long rem;
	while (l > 0 && ret < tto[l]) {
		l--;
		idxInNextNode = sizeof(T) + ret << this->logb;
		if (tto[l] < idxInNextNode)
			idxInNextNode = tto[l];
		levelit[l]->restartFrom(ret);
		ret = levelit[l]->nextUpTo(idxInNextNode);
	}

	if (ret >= tto[l])
		return to;
	return ret;
}

template<typename T>
inline DirectlyAddressedSet::Iterator* MultiLevelDirectlyAddressedSet<T>::newIterator() {
	return new MultiIterator(this);
}

template<typename T>
inline DirectlyAddressedSet::Iterator* MultiLevelDirectlyAddressedSet<T>::newSetIterator(BitMapDirectlyAddressedSet<T> * d, Filter<T> * f) {
	return new MultiIterator(this, d, f);
}

template<typename T>
inline DirectlyAddressedSet::Iterator* MultiLevelDirectlyAddressedSet<T>::newComplIterator() {
	return level[0]->newComplIterator();
}

template<typename T>
inline long MultiLevelDirectlyAddressedSet<T>::newLevel(BitMapDirectlyAddressedSetFactory<T> * f) {
	//create the new level
	int sz = level[h-1]->size();
	sz = (sz >> this->logb) << this->logb == sz? (sz >> this->logb): (sz >> this->logb) + 1;
	level[h++] = f->newInstance(sz);

	return h;
}

template<typename T>
inline long MultiLevelDirectlyAddressedSet<T>::height() {
	return h;
}

template<typename T>
inline long MultiLevelDirectlyAddressedSet<T>::firstInCompl() {
	return level[0]->firstInCompl();
}


template<typename T>
inline long MultiLevelDirectlyAddressedSet<T>::cardOfSet() {
	return level[0]->cardOfSet();
}

template<typename T>
inline long MultiLevelDirectlyAddressedSet<T>::cardOfCompl() {
	return level[0]->cardOfCompl();
}

template<typename T>
inline bool MultiLevelDirectlyAddressedSet<T>::isEmpty() {
	return level[0]->isEmpty();
}

template<typename T>
inline char * MultiLevelDirectlyAddressedSet<T>::toArray(long* size) {
	return level[0]->toArray(size);
}

template<>
inline void MultiLevelDirectlyAddressedSet<int>::show() {
	printf("Estrutura!!! \n");
	for (int i = 0; i < h; i++) {
		printf("vetor no nivel %d : size = %lu \n", i, level[i]->universeSize());
		for (int j = 0; j < level[i]->universeSize(); j++) {
			if (level[i]->isInSet(j))
				printf("(%d)",j);
		}
		printf("\n");
	}
}

template<>
inline void MultiLevelDirectlyAddressedSet<long>::show() {
	printf("Estrutura!!! \n");
	for (int i = 0; i < h; i++) {
		printf("vetor no nivel %d : size = %lu \n", i, level[i]->universeSize());
		for (long j = 0; j < level[i]->universeSize(); j++) {
			if (level[i]->isInSet(j))
				printf("(%lu)",j);
		}
		printf("\n");
	}
}

/*!
 *
 * \sa http://en.wikipedia.org/wiki/Van_Emde_Boas_tree
 *
 */
template <typename T>
class vEBTree : public MultiLevelDirectlyAddressedSet<T> {

};

/*! \class MultiArrayDirectlyAddressedSet
 * \brief A MultiLevelDirectlyAddressedSet implemented with an ArrayBitMapDirectlyAddressedSet per level.
 *
 * The number of levels is fixed.
 *
 */
template <typename T>
class MultiArrayDirectlyAddressedSet : public MultiLevelDirectlyAddressedSet<T> {
public:
	MultiArrayDirectlyAddressedSet(long u, long l) : MultiLevelDirectlyAddressedSet<T>(u) {
		long i;
		for (i = 0; i < l; i++)
			MultiLevelDirectlyAddressedSet<T>::newLevel(new ArrayBitMapDirectlyAddressedSetFactory<T>(u));
	};

	long newLevel(BitMapDirectlyAddressedSetFactory<T> * f) { return -1; };

};

/*! \class MultiArrayDirectlyAddressedSet
 * \brief A MultiLevelDirectlyAddressedSet implemented with a HashBitMapDirectlyAddressedSet at the bottom level and,
 * for the remaining levels, an ArrayBitMapDirectlyAddressedSet per level.
 *
 * The number of levels is fixed and must be at least 2.
 *
 */
template <typename T>
class MultiHashDirectlyAddressedSet : public MultiLevelDirectlyAddressedSet<T> {
public:
	MultiHashDirectlyAddressedSet(long u, long l) : MultiLevelDirectlyAddressedSet<T>(u) {
		if (l < 2)
			return;

		long i;
		MultiLevelDirectlyAddressedSet<T>::newLevel(new HashBitMapDirectlyAddressedSetFactory<T>(u));
		for (i = 1; i < l; i++)
			MultiLevelDirectlyAddressedSet<T>::newLevel(new ArrayBitMapDirectlyAddressedSetFactory<T>(u));
	};

	long newLevel(BitMapDirectlyAddressedSetFactory<T> * f) { return -1; };

};

#endif /* MULTILEVELDIRECTLYADDRESSEDSET_H_ */
